//
// Created by Administrator on 2021/5/29.
//
#include <iostream>
#include <vector>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode *removeLeafNodes(TreeNode *root, int target) {
        if (root == nullptr) return nullptr;
        if (check(root, target)) {
            return nullptr;
        }
        do { root->left = removeLeafNodes(root->left, target); }
        while (check(root->left, target));
        do { root->right = removeLeafNodes(root->right, target); }
        while (check(root->right, target));
        return check(root, target) ? nullptr : root;
    }

    bool check(TreeNode *root, int target) {
        if (root == nullptr) return false;
        return root->left == nullptr and root->right == nullptr and root->val == target;
    }

    void inorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) return;
        inorder(root->left, res); // 对左子节点递归调用
        res.push_back(root->val);
        inorder(root->right, res); // 对右子节点递归调用
    }

    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res; // 结果向量
        inorder(root, res);
        return res;
    }
};

int main() {
    auto n1 = TreeNode(1), n2 = TreeNode(2), n3 = TreeNode(3),
            n4 = TreeNode(2), n5 = TreeNode(2), n6 = TreeNode(4);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n3.left = &n5;
    n3.right = &n6;
    Solution sol;
    auto ans = sol.removeLeafNodes(&n1, 2);
    auto v = sol.inorderTraversal(ans);
    for (auto &x : v) cout << x << endl;
    return 0;
}